package org.nowcoder.leetcode.bit;

import java.util.stream.IntStream;

/**
 * Title  : 338. Counting Bits
 * Source : https://leetcode.cn/problems/counting-bits/description/
 * Author : XrazYang
 * Date   : 2023-10-12
 */

public class LeetCode_338 {
    //Kernighan 算法: 每次进行 n & (n - 1) 操作，都会将 n 的二进制表示中最右边的一个 1 变成 0
    //可用于计算整型数二进制中1的个数
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        IntStream.range(0, n + 1).parallel().forEach(i -> {
            int count = 0;
            int k = i;
            while (i > 0) {
                i = i & (i - 1);
                count++;
            }
            ans[k] = count;
        });
        return ans;
    }
}
